#include <stdio.h>

void shellSort(int arr[], int n)
{
    int gap, i, j, temp;

    // 初始间隔设置为数组长度的一半，然后逐步缩小
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        printf("Gap size: %d\n", gap); // 当前间隔大小

        // 对每个间隔进行插入排序
        for (i = gap; i < n; i++)
        {
            temp = arr[i];

            // 将arr[i]插入到正确位置
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
            {
                arr[j] = arr[j - gap];
            }

            arr[j] = temp;

            // 打印当前步骤
            printf("  Step i=%d: ", i);
            for (int k = 0; k < n; k++)
            {
                printf("%d ", arr[k]);
            }
            printf("\n");
        }

        printf("After gap %d: ", gap);
        for (i = 0; i < n; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n\n");
    }
}

int main()
{
    int arr[] = {64, 25, 12, 22, 11, 9, 37, 42};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i;

    printf("Original array: "); // 原始数组
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    shellSort(arr, n); // 调用希尔排序函数

    printf("\nSorted array: "); // 排序后的数组
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}